Skip to main content

Chapter 6. B-Tree Variants

Copy-on-Write​

Copy-on-write never changes an existing page. It writes a replacement page and keeps references to unaffected pages, so readers can continue using the old version safely. LMDB, a key-value database, uses this approach. It reduces the need to coordinate readers with writers over shared buffers.

Lazy B-Trees (WiredTiger/MongoDB)​

A lazy B-tree collects changes in an update buffer before writing them to disk pages. Reads combine the buffered changes with the cached page; a background thread later merges them, reducing direct competition with foreground reads and writes.

Lazy Adaptative B-Tree​

This approach does the same Lazy B-Tree but to a group of nodes, named subtree. Buffering updates to this subtrees and applying only on those.

  • How does read operations happen in LA B-Trees? Seems to be expensive per BW-Tree.

Flash-Disk Tree ( FD-Tree)​

I honestly didn't grasp much about this Tree variant.

BW Tree (Buzzword Tree)​

The Bw-tree avoids in-place updates by prepending delta nodes—small insert or update records—to a base node through a linked list. A read follows that chain to reconstruct the current page. Nodes are now logical entities. During read, now we need to traverse the entire node LinkedList to construct the node final-state.

This is somewhat similar to what LA-Trees do (see “Lazy-Adaptive Tree”): keeping updates separate from the main structure and replaying them on read.

Petrov, Alex. Database Internals (p. 192). O'Reilly Media. Edição do Kindle.

Examples of BWTrees

Cache Oblivious B-Tree​

  • Not being used in production by any database
  • No implementation outside of academic Creates a Two Level Memory model for all storage - enabling for platform specific configurations but creating something more general.

Take Away Points:

  • B-Trees are not perfect and have a lot of downsides
  • Wired Tigers uses Lazy B-Trees

Further reads

Share: